# Algorithme top-down
# Calcul des poids optimaux

# graphe à traiter
graphe = {"A":1, "B":4, "C":5, "D":4}

def rec_poids_MWIS(G):
    # Fonction récursive
    def f_rec(Gi, i):
        # Cas de base
        if i < 2:
            return A[i]

        # Récursion sur les autres cas
        if i in A.keys():
            return A[i]
        else:
            # Récupère wi
            wi = list(Gi.values())[i-1]

            # Construction de Gi-1
            Gi = {cle: G[cle] for cle in list(G.keys())[0:i-1]}
            S1 = f_rec(Gi,i-1)

            # Construction de Gi-2
            Gi.popitem()
            S2 = f_rec(Gi,i-2) + wi

            A[i] = max(S1,S2)
            return A[i]

    # Poids optimaux des cas de base
    A = {0:0, 1:graphe["A"]}

    # Appel de la fonction récursive
    f_rec(G,len(G))
    return A

A = rec_poids_MWIS(graphe)

print("Algorithme top-down - poids otpimaux")
print("Graphe d'entrée : ",graphe)
print("Valeurs optimales des sous-problèmes : ",A)


def rec_poids_MWIS_avec_comptage(G):
    # Fonction récursive
    def f_rec(Gi, i):
        # Comptage du nombre de récurences
        global nbr_cas
        global nbr_cas_hors_base

        nbr_cas = nbr_cas + 1

        # Cas de base
        if i < 2:
            return A[i]

        # Récursion sur les autres cas
        if i in A.keys():
            return A[i]
        else:
            # Incrémente le nombre de calculs hors cas de base
            nbr_cas_hors_base = nbr_cas_hors_base + 1

            # Récupère wi
            wi = list(Gi.values())[i-1]

            # Construction de Gi-1
            Gi = {cle: G[cle] for cle in list(G.keys())[0:i-1]}
            S1 = f_rec(Gi,i-1)

            # Construction de Gi-2
            Gi.popitem()
            S2 = f_rec(Gi,i-2) + wi

            A[i] = max(S1,S2)
            return A[i]

    # Poids optimaux des cas de base
    A = {0:0, 1:graphe["A"]}

    # Nombre de calculs
    global nbr_cas
    global nbr_cas_hors_base
    nbr_cas = 0
    nbr_cas_hors_base = 0

    # Appel de la fonction récursive
    f_rec(G,len(G))
    return A, nbr_cas, nbr_cas_hors_base


# graphe à traiter
graphe = {"A":3, "B":2, "C":1, "D":6, "E":4, "F":5}
A, nbr_cas, nbr_cas_hors_base = rec_poids_MWIS_avec_comptage(graphe)

print("\nAlgorithme top-down - poids otpimaux")
print("Graphe d'entrée : ",graphe)
print("Valeurs optimales des sous-problèmes : ",A)
print("Nombre de récurences :", nbr_cas)
print("Nombre de calculs hors cas de base :", nbr_cas_hors_base)


# Algorithme bottom-down
# Calcul des poids optimaux

def poids_MWIS_bottom_up(G):
    # Poids optimaux des cas de base
    A = {0:0, 1:G["A"]}

    for i in range(2, len(G)+1):
        A[i] = max(A[i-1],A[i-2] + list(G.values())[i-1])

    return A

# graphe à traiter
graphe = {"A":3, "B":2, "C":1, "D":6, "E":4, "F":5}
A = poids_MWIS_bottom_up(graphe)

print("\nAlgorithme top-down - poids otpimaux")
print("Graphe d'entrée : ",graphe)
print("Valeurs optimales des sous-problèmes : ",A)


# Algorithme de reconstruction

def reconstruction(G,A):
    S = []
    i = len(G)

    while i >= 2:
        if A[i-1] >= A[i-2] + list(G.values())[i-1]:
            i = i-1
        else:
            S.append(list(G.keys())[i-1])
            i = i - 2

    if i == 1:
        S.append(list(G.keys())[0])

    return [S[i] for i in range(len(S)-1,-1,-1)]

# graphe à traiter
graphe = {"A":3, "B":2, "C":1, "D":6, "E":4, "F":5}
A = poids_MWIS_bottom_up(graphe)
S = reconstruction(graphe,A)

print("\nAlgorithme top-down - poids otpimaux")
print("Graphe d'entrée : ",graphe)
print("Valeurs optimales des sous-problèmes : ",A)
print("Chemin pondéré indépendant optimum: ", S)